package algorithm_optimal_solution.LinkedList;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

//复制含有随机指针节点的链表：可以使用哈希表（HashMap），将所有节点复制一个拷贝，拷贝节点只有value属性，key为原节点，value为拷贝节点。
// 再次遍历从哈希表取值将next和rand填充。时间复杂度为O(n)。
//进阶（不使用额外数据结构，时间复杂度O(n)）：为每一个节点生成一个副本节点插入到当前节点后面，设置副本节点的rand为当前节点rand节点的下一个节点，
//最后将所有副本节点脱离原链表组成新链表。
public class CopyRandomNodeLinkedList {

    static class Node{
        private int value;
        private Node node;
        private Node rand;

        public Node(int value, Node node) {
            this.value = value;
            this.node = node;
        }

        public Node(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNode() {
            return node;
        }

        public void setNode(Node node){
            this.node = node;
        }

        public Node getRand() {
            return rand;
        }

        public void setRand(Node rand) {
            this.rand = rand;
        }
    }

    public void copyLinkedList(Node head){
        Node node = head;
        Map<Node,Node> map = new HashMap<>();
        while(node != null){
            map.put(node,new Node(node.getValue()));
            node = node.getNode();
        }
        node = head;
        while(node != null){
            Node copyNode = map.get(node);
            copyNode.setNode(map.get(node.getNode()));
            copyNode.setRand(map.get(node.getRand()));
            node = node.getNode();
        }
        node = map.get(head);
        System.out.println(node == head);
        StringBuilder sb = new StringBuilder();
        while(node != null){
            sb.append(node.getValue()).append(ifNull(node.getNode())).append(ifNull(node.getRand())).append(" ");
            node = node.getNode();
        }
        System.out.println(sb);
    }

    public void copyLinkedListNoMap(Node head){
        if(head == null){
            return;
        }
        Node node = head;
        Node temp;
        while(node != null){
            temp = node.getNode();//暂存B节点
            node.setNode(new Node(node.getValue()));//X节点插入到A节点后
            node.getNode().setNode(temp);//设置X节点的下一个节点为B节点
            node = temp;//当前节点为B节点
        }
        node = head;
        Node copyNode;
        while(node != null){//拷贝节点的rand节点为原节点的rand节点的下一个节点
            temp = node.getNode().getNode();
            copyNode = node.getNode();
            copyNode.setRand(node.getRand() == null ? null : node.getRand().getNode());
            node = temp;
        }
        node = head;
        Node copyHead = head.getNode();
        while(node != null){//拆分
            temp = node.getNode().getNode();
            copyNode = node.getNode();
            copyNode.setNode(temp == null ? null : temp.getNode());//衔接2,4节点
            node.setNode(temp);//衔接1,3节点
            node = temp;//当前节点为3节点
        }
        System.out.println(copyHead == head);
        StringBuilder sb = new StringBuilder();
        while(copyHead != null){
            sb.append(copyHead.getValue()).append(ifNull(copyHead.getNode())).append(ifNull(copyHead.getRand())).append(" ");
            copyHead = copyHead.getNode();
        }
        System.out.println(sb);
    }

    private int ifNull(Node node){
        return node != null ? node.getValue() : 0;
    }

    public static void main(String[] args)throws IOException {
        CopyRandomNodeLinkedList copy = new CopyRandomNodeLinkedList();
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(scanner.readLine());
        String[] numbers = scanner.readLine().split(" ");
        Node node = null;
        Node[] nodes = new Node[len];
        for(int i = len - 1;i >= 0;i--){
            node = new Node(Integer.parseInt(numbers[i]),node);
            nodes[i] = node;
        }
        Node head = node;
        int random;
        while(head != null){
            random = (int)(Math.random()*len);
            head.setRand(nodes[random]);
            head = head.getNode();
        }
        head = node;
        StringBuilder sb = new StringBuilder();
        while(node != null){
            sb.append(node.getValue()).append(copy.ifNull(node.getNode())).append(copy.ifNull(node.getRand())).append(" ");
            node = node.getNode();
        }
        System.out.println(sb);
//        copy.copyLinkedList(head);
        copy.copyLinkedListNoMap(head);
    }
}
